/*  slfnlmul.cpp  by K.Tsuru  */
// function ID = 210    DRADIX, BRADIX
/**************************************************************
SLong and SInteger classes
It provides m*n using a normal method.
It is fast for small figures.
To get the remaindar it uses the quotient, namely a replacemant
rv[i+j] = fType(w - u*rdx); <--- fType(w%rdx);
The different algorithms are used for different radixes.
***************************************************************/
#ifndef SN_H
#include "sn.h"
#endif
static const char* const func = "NLLMult";
SLong NLLMult(const SLong& m, const SLong& n){
//check the signs
    int sgn = m.Sign(210)*n.Sign(210);
    SLong result(m.Type(), 0);
    if(!sgn){   // m = 0 or n = 0
        result.SetZero();
        return result;
    }
    if(m.Type() != n.Type()) m.SetError(m.RADIX_ERR, func, 210);

    uint mh = m.aHead, nh = n.aHead, nt = n.aTail, mt = m.aTail;
    if( (mh+nh+2) >= m.MaxSize() ) m.SetError( m.OVERFLOW_ERR, func, 210);

    result.valloc(mh+nh+2, 0);      // maximum index in roop below

    const fType* mv = m.ReadFigures();
    const fType* nv = n.ReadFigures();
    fType* rv = result.figure.Elements();
//It normalizes simultaneously.
//Here (m_fig + n_fig +1) <= MaxSize-1.
    ulong u, w, lm, rdx = (ulong)m.Radix();
    register uint i, j;

    if(rdx == DRADIX){
        for(i = mt ; i <= mh ; i++){
            u = 0;
            lm = (ulong)mv[i];
            for(j = nt; j <= nh ; j++){
                w = lm*(ulong)nv[j]+(ulong)rv[i+j] + u;
                u = w/rdx;          //carry
                rv[i+j] = fType(w - u*rdx); //faster than fType(w%rdx);
            }
            rv[i+j] = (fType)u;
        }
    } else {
        ulong rdx1 = (ulong)BRADIX1;
        for(i = mt ; i <= mh ; i++){
            u = 0;
            lm = (ulong)mv[i];
            for(j = nt; j <= nh ; j++){
                u += lm*(ulong)nv[j]+(ulong)rv[i+j];
                rv[i+j] = fType(u & rdx1);  // = fType(w%rdx);
                u >>= BRADIX_BITS;          //carry
            }
            rv[i+j] = (fType)u;
        }
    }
//It desides the figure positions.
    uint rt = mt + nt, rh = mh + nh+1;
#ifndef NDEBUG
result.figure(rh);
#endif
    while(!rv[rh]) rh--;
    result.aHead = rh;
    while(!rv[rt]) rt++;
    result.aTail = rt;

    result.SetSign( sgn );
//An extra figure has been taken. It is a rare case.
    if( 2u*(result.aHead+1) <= result.figure.size() ) result.DoCutDown();
    return result;
}